import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class buildTree {
    HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode _buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null)
            return null;

        // 将中序位置信息存入map中
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return dfs(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);

    }

    public TreeNode dfs(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd) {
        if (pStart > pEnd || iStart > iEnd) {
            return null;
        }

        int inPostion = map.get(preorder[pStart]);// pStart preorder中的值，再inorder中的位置
        TreeNode head = new TreeNode(preorder[pStart]);

        // 以 inPostion 分段
        //

        head.left = dfs(preorder, pStart + 1, pStart + (inPostion - iStart), inorder, iStart, inPostion - 1);
        head.right = dfs(preorder, pStart + (inPostion - iStart) + 1, pEnd, inorder, inPostion + 1, iEnd);

        return head;
    }
}
